{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Escape The Ghosts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: escapeGhosts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逃脱阻碍者"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你在进行一个简化版的吃豆人游戏。你从 <code>[0, 0]</code> 点开始出发，你的目的地是&nbsp;<code>target = [x<sub>target</sub>, y<sub>target</sub>]</code> 。地图上有一些阻碍者，以数组 <code>ghosts</code> 给出，第 <code>i</code> 个阻碍者从&nbsp;<code>ghosts[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;出发。所有输入均为 <strong>整数坐标</strong> 。</p>\n",
    "\n",
    "<p>每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 <strong>1 个单位</strong> 的新位置。当然，也可以选择 <strong>不动</strong> 。所有动作 <strong>同时</strong> 发生。</p>\n",
    "\n",
    "<p>如果你可以在任何阻碍者抓住你 <strong>之前</strong> 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者 <strong>同时</strong> 到达了一个位置（包括目的地）&nbsp;<strong>都不算</strong>&nbsp;是逃脱成功。</p>\n",
    "\n",
    "<p>如果不管阻碍者怎么移动都可以成功逃脱时，输出 <code>true</code> ；否则，输出 <code>false</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ghosts = [[1,0],[0,3]], target = [0,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ghosts = [[1,0]], target = [2,0]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ghosts = [[2,0]], target = [1,0]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>阻碍者可以和你同时达到目的地。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ghosts.length &lt;= 100</code></li>\n",
    "\t<li><code>ghosts[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>同一位置可能有 <strong>多个阻碍者</strong> 。</li>\n",
    "\t<li><code>target.length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x<sub>target</sub>, y<sub>target</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [escape-the-ghosts](https://leetcode.cn/problems/escape-the-ghosts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [escape-the-ghosts](https://leetcode.cn/problems/escape-the-ghosts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0],[0,3]]\\n[0,1]', '[[1,0]]\\n[2,0]', '[[2,0]]\\n[1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        \n",
    "        def manhattan_distance(x: list[int], y: list[int]) -> int:\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "\n",
    "        dist_distance = manhattan_distance([0, 0], target)\n",
    "       \n",
    "        for ghost in ghosts:\n",
    "            \n",
    "            if manhattan_distance(ghost, target) <= dist_distance:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        dis_bean_target = abs(target[0]) + abs(target[1])\n",
    "        min_ghosts_dis = float(inf)\n",
    "        for x, y in ghosts:\n",
    "            min_ghosts_dis = min(min_ghosts_dis, abs(target[0]-x)+abs(target[1]-y))\n",
    "        return dis_bean_target < min_ghosts_dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def menhatdistance(self,x1,x2):\n",
    "        return abs(x1[0]-x2[0])+abs(x1[1]-x2[1])\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        source=[0,0]\n",
    "        a=self.menhatdistance(target,source)\n",
    "        return all(self.menhatdistance(ghost,target)>a for ghost in ghosts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        distance = abs(target[0]) + abs(target[1])\n",
    "        return all(\n",
    "            abs(target[0] - x) + abs(target[1] - y) > distance for x, y in ghosts\n",
    "        )\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        #direction = [(-1,0),(1,0),(0,1),(0,-1)]\n",
    "        path = abs(target[0]) + abs(target[1])\n",
    "        path_g = []\n",
    "        for g in ghosts:\n",
    "            path_g.append(abs(g[0]-target[0]) + abs(g[1]-target[1]))\n",
    "        if any([x <= path for x in path_g]):\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        source = [0, 0]\n",
    "        distance = self.manhattanDistance(source, target)\n",
    "        return all(self.manhattanDistance(ghost, target) > distance for ghost in ghosts)\n",
    "    \n",
    "    def manhattanDistance(self, point1, point2):\n",
    "        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dis(a, b):\n",
    "    return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        cor = dis([0,0], target)\n",
    "        for a in ghosts:\n",
    "            if dis(a, target) <= cor:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        target_m = abs(target[0]) + abs(target[1])\n",
    "\n",
    "        for x,y in ghosts:\n",
    "            if abs(target[0] - x) + abs(target[1] - y) <= target_m:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        cur = abs(target[0]) + abs(target[1])\n",
    "        tx, ty = target\n",
    "        for i,j in ghosts:\n",
    "            if abs(tx - i) + abs(ty - j) <= cur:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        deadLine = abs(target[0]) + abs(target[1])\n",
    "        for x, y in ghosts:\n",
    "            if abs(x - target[0]) + abs(y - target[1]) <= deadLine:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        min=abs(target[0])+abs(target[1])\n",
    "        for i in range(len(ghosts)):\n",
    "            if abs(ghosts[i][0]-target[0])+abs(ghosts[i][1]-target[1])<=min:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        def dist(a, b):\n",
    "            return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "        t = abs(target[0]) + abs(target[1])\n",
    "        for g in ghosts:\n",
    "            d = dist(g, target)\n",
    "            if d <= t:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        res=0\n",
    "        for i in ghosts:\n",
    "            if abs(target[0]-i[0])+abs(target[1]-i[1])<=abs(target[0])+abs(target[1]):\n",
    "                res+=1\n",
    "        if res==0:\n",
    "            return True\n",
    "        else :\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# ghost block the door\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        t = abs(target[0]) + abs(target[1])\n",
    "        catch = inf\n",
    "\n",
    "        def dist(source, target):\n",
    "            return abs(source[0] - target[0]) + abs(source[1] - target[1])\n",
    "        for ghost in ghosts:\n",
    "            catch = min(catch, dist(ghost, target) - 1)\n",
    "        \n",
    "        if catch < t:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        cur = abs(target[0]) + abs(target[1])\n",
    "        for i,j in ghosts:\n",
    "            if abs(target[0] - i) + abs(target[1] - j) <= cur:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        def getDist(pos:List[int] , target:List[int]) -> int:\n",
    "            return abs(pos[0] - target[0]) + abs(pos[1] - target[1])\n",
    "        myDist = getDist([0,0] , target)\n",
    "        for ghost in ghosts:\n",
    "            if getDist(ghost,target) <= myDist :\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        k = abs(target[0]) + abs(target[1])\n",
    "        for x, y in ghosts:\n",
    "            if abs(x - target[0]) + abs(y - target[1]) <= k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        tx, ty = target\n",
    "        t = abs(tx) + abs(ty)\n",
    "        for x, y in ghosts:\n",
    "            if abs(tx-x) + abs(ty-y) <= t:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        mi=min([abs(target[0]-x[0])+abs(target[1]-x[1]) for x in ghosts])\n",
    "        \n",
    "        return abs(target[0])+abs(target[1])<mi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        pacman_distance = abs(target[0]) + abs(target[1])\n",
    "\n",
    "        for ghost in ghosts:\n",
    "            ghost_distance = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])\n",
    "            if ghost_distance <= pacman_distance:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        distance = self.manhatten_distance(target, [0, 0])\n",
    "        return all(self.manhatten_distance(ghost, target) > distance for ghost in ghosts)\n",
    "\n",
    "    def manhatten_distance(self, point1: List[int], point2: List[int]) -> int:\n",
    "        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        return all([abs(target[0])+abs(target[1]) < abs(ghost[0]-target[0])+abs(ghost[1]-target[1]) for ghost in ghosts])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        ghostMinDistance = min([abs(x - target[0]) + abs(y - target[1]) for x,y in ghosts])\n",
    "        return abs(target[0]) + abs(target[1]) < ghostMinDistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        #算曼哈顿距离\n",
    "        me=abs(target[0])+abs(target[1])\n",
    "        cur=inf\n",
    "        for x,y in ghosts:\n",
    "            cur=min(cur,abs(x-target[0])+abs(y-target[1]))\n",
    "            if cur<=me:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        def manhattan(p1: List[int], p2: List[int]) -> int:\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "        d0 = manhattan([0, 0], target)\n",
    "        for p in ghosts:\n",
    "            di = manhattan(p, target)\n",
    "            if di <= d0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        dis = abs(target[0]) + abs(target[1])\n",
    "        for g in ghosts:\n",
    "            dis1 = abs(target[0] - g[0]) + abs(target[1] - g[1])\n",
    "            if dis1 <= dis:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        #算曼哈顿距离,只要有阻碍者比你先到或一样到就不行\n",
    "        me=abs(target[0])+abs(target[1])\n",
    "        cur=inf\n",
    "        for x,y in ghosts:\n",
    "            cur=min(cur,abs(x-target[0])+abs(y-target[1]))\n",
    "            if cur<=me:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        xt, yt = target\n",
    "        return all(abs(xt) + abs(yt) < abs(xt-xg) + abs(yt-yg) for xg, yg in ghosts)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        distance = abs(target[0]) + abs(target[1])\n",
    "        for x, y in ghosts:\n",
    "            if abs(target[0] - x) + abs(target[1] - y) <= distance:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        source = [0, 0]\n",
    "        distance = manhattanDistance(source, target)\n",
    "        return all(manhattanDistance(ghost, target) > distance for ghost in ghosts)\n",
    "\n",
    "def manhattanDistance(point1: List[int], point2: List[int]) -> int:\n",
    "    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        source=[0,0]\n",
    "        distance=manhattanDistance(source,target)\n",
    "        return all(manhattanDistance(ghost,target)>distance for ghost in ghosts)\n",
    "    \n",
    "def manhattanDistance(point1,point2):\n",
    "    return abs(point1[0]-point2[0])+abs(point1[1]-point2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "      def dis(a,b):\n",
    "        return abs(a[0]-b[0]) + abs(a[1]-b[1])\n",
    "      a = dis([0,0],target)\n",
    "      b = min(dis(g,target) for g in ghosts)\n",
    "      return b > a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        dist1=abs(target[0])+abs(target[1])\n",
    "        for i in ghosts:\n",
    "            dist2=abs(i[0]-target[0])+abs(i[1]-target[1])\n",
    "            if dist1>=dist2:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        # 与小鬼同步移动，我距离终点更近即可到达\n",
    "        my_dis = abs(target[0]) + abs(target[1])\n",
    "        for ghost in ghosts:\n",
    "            if abs(ghost[0]-target[0]) + abs(ghost[1]-target[1]) <= my_dis:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\r\n",
    "        steps = abs(target[0]) + abs(target[1])\r\n",
    "        for gx, gy in ghosts:\r\n",
    "            step = abs(gx - target[0]) + abs(gy - target[1])\r\n",
    "            if step <= steps:\r\n",
    "                return False\r\n",
    "        return True\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        def distance(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "\n",
    "        my_distance = distance([0, 0], target)\n",
    "        for ghost in ghosts:\n",
    "            ghost_distance = distance(ghost, target)\n",
    "            if ghost_distance <= my_distance:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        distance = abs(target[0]) + abs(target[1])\n",
    "        nums = 1\n",
    "        for i in ghosts:\n",
    "            if abs(i[0] - target[0]) + abs(i[1]-target[1]) <= distance:\n",
    "                nums = 0\n",
    "            else:\n",
    "                continue\n",
    "        if nums == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        td = abs(target[0]) + abs(target[1])\n",
    "\n",
    "        for ghost in ghosts:\n",
    "            gd = abs(target[0] - ghost[0]) + abs(target[1] - ghost[1])\n",
    "            if gd <= td:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        def calx(a,b,c,d):\n",
    "            return abs(a-c)+abs(b-d)\n",
    "        x,y=target[0],target[1]\n",
    "        dis=calx(0,0,x,y)\n",
    "        for a,b in ghosts:\n",
    "            d=calx(a,b,x,y)\n",
    "            if d<=dis:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        dis = abs(target[0]) + abs(target[1])\n",
    "        for a, b in ghosts:\n",
    "            s = abs(a - target[0]) + abs(b - target[1])\n",
    "            if s <= dis:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        l=abs(target[0])+abs(target[1])\n",
    "        for i in ghosts:\n",
    "            if abs(i[0]-target[0])+abs(i[1]-target[1])<=l:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        分别计算豆人和阻碍者到目标点的距离\n",
    "        如果豆人距离目标点近, True\n",
    "        \"\"\"\n",
    "        # 豆人距离目标点距离\n",
    "        dis_bean = abs(target[0]) + abs(target[1])\n",
    "        # 计算阻碍者距离目标点的距离\n",
    "        for x, y in ghosts:\n",
    "            dis_ghosts = abs(target[0]-x)+abs(target[1]-y)\n",
    "            if dis_ghosts <= dis_bean:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        short_distance = abs(target[0] - 0) + abs(target[1] - 0)\n",
    "        for x, y in ghosts:\n",
    "            dis = abs(x - target[0]) + abs(y - target[1])\n",
    "            if dis <= short_distance:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        deadLine = abs(target[0]) + abs(target[1])\n",
    "        for x, y in ghosts:\n",
    "            if abs(x - target[0]) + abs(y - target[1]) <= deadLine:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        distanace = abs(target[0]) + abs(target[1])\n",
    "        for ghost in ghosts:\n",
    "            if abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]) <= distanace:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:\n",
    "        source = [0, 0]\n",
    "        distance = manhattanDistance(source, target)\n",
    "        return all(manhattanDistance(ghost, target) > distance for ghost in ghosts)\n",
    "\n",
    "def manhattanDistance(point1: List[int], point2: List[int]) -> int:\n",
    "    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
